package pers.qianyu.month_202012.date_20201203;

import org.junit.*;

import java.util.*;

/**
 * 435. 无重叠区间
 * https://leetcode-cn.com/problems/non-overlapping-intervals/
 *
 * @author mizzle rain
 * @date 2020-12-03 17:18
 */
public class EraseOverlapIntervals {
    public int eraseOverlapIntervals(int[][] intervals) {
        int res = 0;
        Arrays.sort(intervals, (arr1, arr2) -> arr1[1] - arr2[1]);
        int i = 0;
        while (i < intervals.length) {
            int k = i + 1;
            while (k < intervals.length) {
                if (intervals[i][1] > intervals[k][0]) {
                    res++;
                    k++;
                } else {
                    break;
                }
            }
            i = k;
        }
        return res;
    }

    public int eraseOverlapIntervals2(int[][] intervals) {
        int len = intervals.length;
        if (len == 0) return 0;
        Arrays.sort(intervals, (arr1, arr2) -> arr1[1] - arr2[1]);
        int end = intervals[0][1], count = 1;
        for (int[] interval : intervals) {
            if (interval[0] >= end) {
                count++;
                end = interval[1];
            }
        }
        return len - count;
    }

    @Test
    public void test1() {
        int[][] param = {
                {1, 2}, {2, 3}, {3, 4}, {1, 3}
        };
        int result = new EraseOverlapIntervals().eraseOverlapIntervals(param);
        System.out.println("result = " + result);
    }

    @Test
    public void test2() {
        int[][] param = {
                {1, 2}, {1, 2}, {1, 2}
        };
        int result = new EraseOverlapIntervals().eraseOverlapIntervals(param);
        System.out.println("result = " + result);
    }

    @Test
    public void test3() {
        int[][] param = {
                {0, 2}, {1, 3}, {2, 4}, {3, 5}, {4, 6}
        };
        int result = new EraseOverlapIntervals().eraseOverlapIntervals(param);
        System.out.println("result = " + result);
    }
}
